#include <iostream>
#include <vector>

using namespace std;

vector<int> memo;   // memo[i]就记忆了第i个值
int num = 0;
// 递归求斐波那契数列
// 记忆化搜索
int fib( int n ){
    num++;

    if( n == 0 )
        return 0;

    if( n == 1 )
        return 1;

    if(memo[n] == -1)   // 之前没有计算过 f(n)
        memo[n] = fib(n-1) + fib(n-2);

    return memo[n];
}

int main() {
    num = 0;

    int n = 1000;
    memo = vector<int>(n+1,-1); // 开始的时候一个数字都没计算出来
    time_t startTime = clock();
    int res = fib(n);
    time_t endTime = clock();

    cout << "fib(" << n << ") = " << res << endl;
    cout << "time : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s" << endl;
    cout << "run function fib() " << num << "times." << endl;
    return 0;
}